{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #文物朝代判断"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkDynasty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #文物朝代判断"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>展览馆展出来自 13 个朝代的文物，每排展柜展出 5 个文物。某排文物的摆放情况记录于数组 <code>places</code>，其中 <code>places[i]</code> 表示处于第 <code>i</code> 位文物的所属朝代编号。其中，编号为 0 的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否连续（如遇未知朝代可算作连续情况）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>places = [0, 6, 9, 0, 7]\n",
    "<strong>输出: </strong>True\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>places = [7, 8, 9, 10, 11]\n",
    "<strong>输出:</strong> True\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>places.length = 5</code></li>\n",
    "\t<li><code>0 &lt;= places[i] &lt;= 13</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bu-ke-pai-zhong-de-shun-zi-lcof](https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bu-ke-pai-zhong-de-shun-zi-lcof](https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        mini, maxi = 14, 0\n",
    "        num_zero = 0\n",
    "        s = set()\n",
    "        for i in places:\n",
    "            if i in s:\n",
    "                return False\n",
    "            if i != 0:\n",
    "                mini = min(i, mini)\n",
    "                maxi = max(i, maxi)\n",
    "                s.add(i)\n",
    "        if maxi- mini <= 4:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        joker=0\n",
    "        places.sort()\n",
    "        for i in range(len(places)-1):\n",
    "            if places[i]==0:\n",
    "                joker+=1\n",
    "            if places[i]==places[i+1] and places[i]!=0:\n",
    "                return False\n",
    "        return places[4]-places[joker]<5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, place: List[int]) -> bool:\n",
    "        unknown = 0\n",
    "        seen = set()\n",
    "        mx, mi = 0,14\n",
    "        for i in range(0,5):\n",
    "            \n",
    "            if place[i] == 0:\n",
    "                unknown += 1\n",
    "            elif place[i] in seen:\n",
    "                return False\n",
    "            else:\n",
    "                mx = place[i] if place[i] > mx  else mx\n",
    "                mi = place[i] if place[i] < mi  else mi\n",
    "                seen.add(place[i])\n",
    "        print(mx,mi)\n",
    "        if mx - mi <= 4:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, place: List[int]) -> bool:\n",
    "        place.sort(reverse=True)\n",
    "        i = 0\n",
    "        pre = 0\n",
    "        while i < 5 and place[i] != 0:\n",
    "            if pre == place[i]:\n",
    "                return False\n",
    "            \n",
    "            pre = place[i]\n",
    "            i += 1            \n",
    "        \n",
    "        if i < 5:\n",
    "            return place[0] - place[i - 1] <= 4\n",
    "        else:\n",
    "            return place[0] - place[4] <= 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "\n",
    "        #如果有0则直接跳过，\n",
    "        #利用集合set来实现遍历判重，\n",
    "        #借助辅助变量ma和mi来遍历获取最大值最小值\n",
    "\n",
    "        repeat = set()\n",
    "        mi, ma = 14, 0\n",
    "        for p in places:\n",
    "            if p == 0: \n",
    "                continue\n",
    "            ma = max(ma, p)\n",
    "            mi = min(mi, p)\n",
    "            if p in repeat:\n",
    "                return False\n",
    "            repeat.add(p)\n",
    "        if ma - mi < 5:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        cnt = 0\n",
    "        seen = []\n",
    "        places.sort()\n",
    "        for i in places:\n",
    "            if i == 0:\n",
    "                cnt += 1\n",
    "            elif i in seen:          \n",
    "                return False\n",
    "            else:\n",
    "                seen.append(i)\n",
    "        if places[-1] - places[cnt] <= 4:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        new_lst=[x for x in places if x != 0]\n",
    "        new_zero=[x for x in places if x == 0]\n",
    "        if max(new_lst)-min(new_lst)>len(set(new_lst))+len(new_zero):return False\n",
    "        if len(new_lst)>len(set(new_lst)): return False\n",
    "        if max(new_lst)-min(new_lst)>4: return False\n",
    "        \n",
    "        return True\n",
    "'''\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue # 跳过未知朝代\n",
    "            ma = max(ma, place) # 最大编号朝代\n",
    "            mi = min(mi, place) # 最小编号朝代\n",
    "            if place in repeat: return False # 若有重复，提前返回 false\n",
    "            repeat.add(place) # 添加朝代至 Set\n",
    "        return ma - mi < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续 \n",
    "'''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        count=0\n",
    "        i=0\n",
    "        n=len(places)\n",
    "        places=sorted(places)\n",
    "        for i in range(len(places)):\n",
    "            if places[i]!=0:break\n",
    "            count +=1\n",
    "        while (i+1)<n:\n",
    "            need=places[i+1]-places[i]-1\n",
    "            if need<0:\n",
    "                return False\n",
    "            count-=need\n",
    "            if count<0:\n",
    "                return False\n",
    "            i+=1\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places_set = set()\n",
    "        max_p, min_p = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0:\n",
    "                continue\n",
    "            max_p = max(max_p, place)\n",
    "            min_p = min(min_p, place)\n",
    "            if place in places_set:\n",
    "                return False\n",
    "            places_set.add(place)\n",
    "        return max_p - min_p < 5\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        new_lst=[x for x in places if x != 0]\n",
    "        new_zero=[x for x in places if x == 0]\n",
    "        if max(new_lst)-min(new_lst)>4: return False\n",
    "        if len(new_lst)>len(set(new_lst)): return False\n",
    "        if 5!=len(set(new_lst))+len(new_zero):return False\n",
    "        \n",
    "        return True\n",
    "'''\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue # 跳过未知朝代\n",
    "            ma = max(ma, place) # 最大编号朝代\n",
    "            mi = min(mi, place) # 最小编号朝代\n",
    "            if place in repeat: return False # 若有重复，提前返回 false\n",
    "            repeat.add(place) # 添加朝代至 Set\n",
    "        return ma - mi < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续 \n",
    "'''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        _min = 1e10\n",
    "        _max = -1\n",
    "        seen = set()\n",
    "        for num in places:\n",
    "            if num == 0: continue\n",
    "            if num in seen:\n",
    "                return False\n",
    "            seen.add(num)\n",
    "            if num < _min: _min = num\n",
    "            if num > _max: _max = num\n",
    "        return _max - _min < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places.sort()\n",
    "        tibu=0\n",
    "        for j in places:\n",
    "            if j==0:\n",
    "                tibu+=1\n",
    "        if max(places)-min(places[tibu:])>5:\n",
    "            return False\n",
    "        for i in range(4):\n",
    "            if places[i]==0:\n",
    "                tibu+=1\n",
    "            elif places[i]==places[i+1]:\n",
    "                return False\n",
    "            elif places[i]!=places[i+1]-1:\n",
    "                if tibu==0:\n",
    "                    return False\n",
    "                else:\n",
    "                    tibu-=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, nums: List[int]) -> bool:\n",
    "        ns = [x for x in nums if x != 0]\n",
    "        ns.sort()\n",
    "        l1,l2 = len(nums),len(ns)\n",
    "        dis = 0\n",
    "        for i in range(1,l2):\n",
    "            if ns[i] == ns[i-1]:\n",
    "                return False\n",
    "            elif ns[i] - ns[i-1] > 1:\n",
    "                dis += ns[i] - ns[i-1] - 1\n",
    "        return dis <= (l1-l2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places.sort()\n",
    "        i = 0\n",
    "        while i<len(places):\n",
    "            if places[i] == 0:i+=1\n",
    "            else:break\n",
    "        if i == len(places)-1:return True\n",
    "        notzero = places[i:]\n",
    "        b=set(notzero)\n",
    "        if len(b) == len(notzero) and notzero[-1] - notzero[0] <=4:return True\n",
    "        else:return False\n",
    "\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        unknown = 0\n",
    "        places.sort() # 数组排序\n",
    "        for i in range(4):\n",
    "            if places[i] == 0: unknown += 1 # 统计未知朝代数量\n",
    "            elif places[i] == places[i + 1]: return False # 若有重复，提前返回 false\n",
    "        return places[4] - places[unknown] < 5 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        count=0\n",
    "        i=0\n",
    "        n=len(places)\n",
    "        places=sorted(places)\n",
    "        for i in range(len(places)):\n",
    "            if places[i]!=0:break\n",
    "            count +=1\n",
    "        while (i+1)<n:\n",
    "            need=places[i+1]-places[i]-1\n",
    "\n",
    "            if need<0:\n",
    "                return False\n",
    "            count-=need\n",
    "            if count<0:\n",
    "                return False\n",
    "            i+=1\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, place: List[int]) -> bool:\n",
    "        cnt = set()\n",
    "        maximum = -inf\n",
    "        minimum = inf\n",
    "        for num in place:\n",
    "            if num in cnt:\n",
    "                return False\n",
    "            if num == 0:\n",
    "                continue\n",
    "            maximum = max(num, maximum)\n",
    "            minimum = min(num, minimum)\n",
    "            cnt.add(num)\n",
    "        return maximum-minimum < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        min_val, max_val = float('inf'), float('-inf')\n",
    "        num_set = set()\n",
    "        for place in places:\n",
    "            if place == 0:\n",
    "                continue\n",
    "            \n",
    "            if place in num_set:\n",
    "                return False\n",
    "            \n",
    "            min_val = min(min_val, place)\n",
    "            max_val = max(max_val, place)\n",
    "            num_set.add(place)\n",
    "\n",
    "        return max_val-min_val<=4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repet = set()\n",
    "        xiao = 13\n",
    "        da = 0\n",
    "        for i in places:\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if i not in repet:\n",
    "                repet.add(i)\n",
    "            else:\n",
    "                return False\n",
    "            if i > da:\n",
    "                da = i\n",
    "            if i<xiao:\n",
    "                xiao = i\n",
    "        print(da)\n",
    "        print(xiao)\n",
    "        if da-xiao>=5:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        # 遍历列表，用set存储，有重复返回False\n",
    "        ma = 0\n",
    "        mi = 14\n",
    "        s = set()\n",
    "        for place in places:\n",
    "            if place == 0:\n",
    "                continue\n",
    "            elif place in s:\n",
    "                return False\n",
    "            else:\n",
    "                s.add(place)\n",
    "                ma = max(place, ma)\n",
    "                mi = min(place, mi)\n",
    "        if ma - mi < 5:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue\n",
    "            ma = max(ma, place)\n",
    "            mi = min(mi, place)\n",
    "            if place in repeat: return False\n",
    "            repeat.add(place)\n",
    "        return ma - mi < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        hmap = {}\n",
    "        for i in places:\n",
    "            if i == 0:\n",
    "                continue\n",
    "            else:\n",
    "                if i not in hmap:\n",
    "                    hmap[i] = 1\n",
    "                else:\n",
    "                    hmap[i] += 1\n",
    "        for j in hmap:\n",
    "            if hmap[j] == 1:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        if max(hmap) - min(hmap) < 5:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        ma, mi = 0, 14\n",
    "        repeat = {}\n",
    "\n",
    "        for place in places:\n",
    "            if place == 0:\n",
    "                continue\n",
    "            if place > ma:\n",
    "                ma = place\n",
    "            if place < mi:\n",
    "                mi = place\n",
    "            if place in repeat:\n",
    "                return False\n",
    "            repeat[place] = 1\n",
    "        \n",
    "        if ma - mi < 5:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        ma = 0\n",
    "        mi = 14\n",
    "        real_num = set()\n",
    "        for place in places:\n",
    "            if place == 0: continue\n",
    "            ma = max(ma,place)\n",
    "            mi = min(mi,place)\n",
    "            if place in real_num: return False\n",
    "            real_num.add(place)\n",
    "        return ma - mi <5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        zeros = nums.count(0)\n",
    "        for i in range(zeros+1, len(nums)):\n",
    "            count = nums[i] - nums[i-1]\n",
    "            if count == 1:\n",
    "                continue\n",
    "            elif count == 0:\n",
    "                return False\n",
    "            else:\n",
    "                zeros -= count - 1\n",
    "                if zeros < 0:\n",
    "                    return False\n",
    "        if i == len(nums) - 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        unknown = 0\n",
    "        places.sort() # 数组排序\n",
    "        for i in range(4):\n",
    "            if places[i] == 0: unknown += 1 # 统计未知朝代数量\n",
    "            elif places[i] == places[i + 1]: return False # 若有重复，提前返回 false\n",
    "        return places[4] - places[unknown] < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        mini, maxi = 14, 0\n",
    "        num_zero = 0\n",
    "        s = set()\n",
    "        for i in places:\n",
    "            if i in s:\n",
    "                return False\n",
    "            if i == 0:\n",
    "                num_zero += 1\n",
    "            else:\n",
    "                mini = min(i, mini)\n",
    "                maxi = max(i, maxi)\n",
    "                s.add(i)\n",
    "        if maxi- mini <= 4:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        hs = []\n",
    "        for i in range(len(places)):\n",
    "            if places[i] == 0:\n",
    "                continue\n",
    "            elif places[i] in hs:\n",
    "                return False\n",
    "            else:\n",
    "                hs.append(places[i])\n",
    "        if max(hs)-min(hs)<5:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]):\n",
    "        zero_list = []\n",
    "        no_zero_list = []\n",
    "        min_val, max_val = float(\"inf\"), float(\"-inf\")\n",
    "        for x in places:\n",
    "            if x == 0:\n",
    "                zero_list.append(x)\n",
    "            else:\n",
    "                min_val = min(min_val, x)\n",
    "                max_val = max(max_val, x)\n",
    "                no_zero_list.append(x)\n",
    "        full_list = range(min_val, max_val+1)\n",
    "        # print(full_list)\n",
    "        return len(set(no_zero_list)) == len(no_zero_list) and len(set(full_list) - set(no_zero_list)) <= len(zero_list)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places.sort()\n",
    "        c=0\n",
    "        for i in range(4):\n",
    "            if places[i]==0:\n",
    "                c+=1\n",
    "                continue\n",
    "            else:\n",
    "                if places[i+1]==places[i]:\n",
    "                    return False\n",
    "                else:\n",
    "                    t= places[i+1]-places[i]\n",
    "                    c-=(t-1)\n",
    "        return c>=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        min = float(\"inf\")\n",
    "        max = 0\n",
    "        cache = []\n",
    "        for i in places:\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if i in cache:\n",
    "                return False\n",
    "            if i < min:\n",
    "                min = i\n",
    "            if max < i :\n",
    "                max = i\n",
    "\n",
    "            cache.append(i)\n",
    "\n",
    "        return (max-min) <= 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue # 跳过未知朝代\n",
    "            ma = max(ma, place) # 最大编号朝代\n",
    "            mi = min(mi, place) # 最小编号朝代\n",
    "            if place in repeat: return False # 若有重复，提前返回 false\n",
    "            repeat.add(place) # 添加朝代至 Set\n",
    "        return ma - mi < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue # 跳过未知朝代\n",
    "            ma = max(ma, place) # 最大编号朝代\n",
    "            mi = min(mi, place) # 最小编号朝代\n",
    "            if place in repeat: return False # 若有重复，提前返回 false\n",
    "            repeat.add(place) # 添加朝代至 Set\n",
    "        return ma - mi < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        N = len(nums) - 1\n",
    "        total = 0\n",
    "        zeros = nums.count(0)\n",
    "        total = nums[-1] - nums[zeros]\n",
    "        temp = nums[zeros]\n",
    "        if len(set(nums[zeros:])) != len(nums) - zeros:\n",
    "            return False\n",
    "        print(N, total)\n",
    "        if  0 <= N-total <= zeros:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places.sort()\n",
    "        zero, index = 0, 0\n",
    "        while index < 5:\n",
    "            while places[index] == 0:\n",
    "                zero += 1\n",
    "                index += 1\n",
    "            break\n",
    "        if (5-index) != len(set(places[index:])):\n",
    "            return False\n",
    "        for i in range(places[index], places[4]+1):\n",
    "            if i in places:\n",
    "                continue\n",
    "            zero -= 1\n",
    "            if zero < 0:\n",
    "                return False\n",
    "        return True    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue # 跳过未知朝代\n",
    "            ma = max(ma, place) # 最大编号朝代\n",
    "            mi = min(mi, place) # 最小编号朝代\n",
    "            if place in repeat: return False # 若有重复，提前返回 false\n",
    "            repeat.add(place) # 添加朝代至 Set\n",
    "        return ma - mi < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        visited = set()\n",
    "        minVal, maxVal = 14, 0\n",
    "        for place in places:\n",
    "            if place == 0:\n",
    "                continue\n",
    "            minVal = min(minVal, place)\n",
    "            maxVal = max(maxVal, place)\n",
    "            if place in visited:\n",
    "                return False\n",
    "            visited.add(place)\n",
    "        return (maxVal - minVal) < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places.sort()\n",
    "        num=0\n",
    "        # 0的数量\n",
    "        num=places.count(0)\n",
    "        # 不连续的数量\n",
    "        number=0\n",
    "        for i in range(num,4):\n",
    "            if places[i]!=places[i+1]-1 :\n",
    "                number+=places[i+1]-places[i]\n",
    "            if places[i]==places[i+1]:\n",
    "                return False\n",
    "        if number >num +1:\n",
    "            return False\n",
    "        else:\n",
    "            return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, nums: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for num in nums:\n",
    "            if num == 0: continue\n",
    "            ma = max(ma, num)\n",
    "            mi = min(mi, num)\n",
    "            if num in repeat: return False\n",
    "            repeat.add(num)\n",
    "        return ma - mi < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for i in range(len(places)):\n",
    "            if places[i] == 0: continue\n",
    "            ma = max(ma, places[i])\n",
    "            mi = min(mi, places[i])\n",
    "            if places[i] in repeat: return False\n",
    "            repeat.add(places[i])\n",
    "        return ma - mi < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for item in places:\n",
    "            if item == 0: continue\n",
    "            ma = max(ma, item)\n",
    "            mi = min(mi, item)\n",
    "            if item in repeat: return False\n",
    "            repeat.add(item)      \n",
    "        return ma - mi < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def checkDynasty(self, places: List[int]) -> bool:\n",
    "#         hs = []\n",
    "#         for i in range(len(places)):\n",
    "#             if places[i] == 0:\n",
    "#                 continue\n",
    "#             elif places[i] in hs:\n",
    "#                 return False\n",
    "#             else:\n",
    "#                 hs.append(places[i])\n",
    "#         if max(hs)-min(hs)<5:\n",
    "#             return True\n",
    "#         else:\n",
    "#             return False\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue # 跳过未知朝代\n",
    "            ma = max(ma, place) # 最大编号朝代\n",
    "            mi = min(mi, place) # 最小编号朝代\n",
    "            if place in repeat: return False # 若有重复，提前返回 false\n",
    "            repeat.add(place) # 添加朝代至 Set\n",
    "        return ma - mi < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue # 跳过未知朝代\n",
    "            ma = max(ma, place) # 最大编号朝代\n",
    "            mi = min(mi, place) # 最小编号朝代\n",
    "            if place in repeat: return False # 若有重复，提前返回 false\n",
    "            repeat.add(place) # 添加朝代至 Set\n",
    "        return ma - mi < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        hs = []\n",
    "        for i in range(len(places)):\n",
    "            if places[i] == 0:\n",
    "                continue\n",
    "            elif places[i] in hs:\n",
    "                return False\n",
    "            else:\n",
    "                hs.append(places[i])\n",
    "        if max(hs)-min(hs)<5:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue\n",
    "            ma = max(ma, place)\n",
    "            mi = min(mi, place)\n",
    "            if place in repeat: return False\n",
    "            repeat.add(place)\n",
    "        return ma - mi < 5\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places.sort()\n",
    "        i = 0\n",
    "        while i<len(places):\n",
    "            if places[i] == 0:i+=1\n",
    "            else:break\n",
    "        if i == len(places)-1:return True\n",
    "        notzero = places[i:]\n",
    "        b=set(notzero)\n",
    "        if len(b) == len(notzero) and notzero[-1] - notzero[0] <=4:return True\n",
    "        else:return False\n",
    "\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        hs = {}\n",
    "        for place in places:\n",
    "            if place in hs:\n",
    "                hs[place] += 1\n",
    "            else:\n",
    "                hs[place] = 1\n",
    "            if hs[place] >1 and place != 0:\n",
    "                return False\n",
    "        pt = 0\n",
    "        for _ in range(len(places)):\n",
    "            if places[pt] == 0:\n",
    "                places.pop(pt)\n",
    "            else:\n",
    "                pt += 1\n",
    "        if max(places) - min(places) > 4:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        numbers = sorted(places)\n",
    "        zeros = 0\n",
    "        gap = 0\n",
    "        for i in range(len(numbers)-1):\n",
    "            if numbers[i] == 0:\n",
    "                zeros += 1\n",
    "            else:\n",
    "                if numbers[i+1]-numbers[i] == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    gap += numbers[i+1]-numbers[i]-1\n",
    "        if gap > zeros:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places = sorted(places)\n",
    "        unknow = places.count(0)\n",
    "        before = places[unknow]\n",
    "        for i in range(unknow+1, 5):\n",
    "            # print(places[i], before, unknow)\n",
    "            if places[i] > before+1 :\n",
    "                cha = places[i] - before - 1\n",
    "                if unknow-cha >= 0 :\n",
    "                    unknow -= cha\n",
    "                    before = places[i]\n",
    "                else:\n",
    "                    return False\n",
    "            elif places[i] == before+1:\n",
    "                before += 1\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        num0=0\n",
    "        s=set()\n",
    "        for i in places:\n",
    "            if i==0:\n",
    "                num0+=1\n",
    "            else:\n",
    "                if i in s:\n",
    "                    return False\n",
    "                s.add(i)\n",
    "        return max(s)-min(s)+1<=len(s)+num0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        mi, ma = 14, 0\n",
    "        duplicated = set()\n",
    "        for p in places:\n",
    "            if p == 0: continue\n",
    "            if p in duplicated: return False\n",
    "            mi, ma = min(mi, p), max(ma, p)\n",
    "            duplicated.add(p)\n",
    "        print\n",
    "        return ma - mi < len(places)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        unknow = 0\n",
    "        places.sort()\n",
    "        for i in range(4):\n",
    "            if places[i] == 0: unknow += 1\n",
    "            elif places[i] == places[i+1]: return False\n",
    "        return places[4] - places[unknow] < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        maxi, mini = -1, 14\n",
    "        nums = set()\n",
    "        for i in range(len(places)):\n",
    "            if places[i] == 0 :\n",
    "                pass\n",
    "            else:\n",
    "                if places[i] in nums:\n",
    "                    return False\n",
    "                maxi = max(maxi, places[i])\n",
    "                mini = min(mini, places[i])\n",
    "                nums.add(places[i])\n",
    "        return maxi - mini < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma = 0\n",
    "        mi = 14\n",
    "        for place in places:\n",
    "            if place == 0: continue\n",
    "            if place in repeat: return False\n",
    "            ma = max(ma, place)\n",
    "            mi = min(mi, place)\n",
    "            repeat.add(place)\n",
    "        return ma - mi < 5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        repeat = set()\n",
    "        ma, mi = 0, 14\n",
    "        for place in places:\n",
    "            if place == 0: continue # 跳过未知朝代\n",
    "            ma = max(ma, place) # 最大编号朝代\n",
    "            mi = min(mi, place) # 最小编号朝代\n",
    "            if place in repeat: return False # 若有重复，提前返回 false\n",
    "            repeat.add(place) # 添加朝代至 Set\n",
    "        return ma - mi < 5 # 最大编号朝代 - 最小编号朝代 < 5 则连续 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places.sort()\n",
    "        i = 0\n",
    "        while i<len(places):\n",
    "            if places[i] == 0:i+=1\n",
    "            else:break\n",
    "        if i == len(places)-1:return True\n",
    "        notzero = places[i:]\n",
    "        b=set(notzero)\n",
    "        if len(b) == len(notzero) and notzero[-1] - notzero[0] <=4:return True\n",
    "        else:return False\n",
    "\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        num_list = []\n",
    "        for num in places:\n",
    "            if num == 0:\n",
    "                continue\n",
    "            if num in num_list:\n",
    "                return False\n",
    "            num_list.append(num)\n",
    "        max_num = max(num_list)\n",
    "        min_num = min(num_list)\n",
    "        if max_num - min_num <= 4:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        zero = 0\n",
    "        places.sort()\n",
    "        for i in range(4):\n",
    "            if places[i] == 0:\n",
    "                zero += 1\n",
    "            elif places[i] == places[i + 1]:\n",
    "                return False\n",
    "\n",
    "        return places[4] - places[zero] < 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        places = sorted(places)\n",
    "        zero = 0\n",
    "        for i in range(len(places)):\n",
    "            if places[i] == 0:\n",
    "                zero += 1\n",
    "            else:\n",
    "                break\n",
    "        for j in range(i, len(places) - 1):\n",
    "            d = places[j + 1] - places[j]\n",
    "            if d == 0: return False\n",
    "            zero -= (d - 1)\n",
    "            if zero >= 0: continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, places: List[int]) -> bool:\n",
    "        hmap = {}\n",
    "        for i in places:\n",
    "            if i == 0:\n",
    "                continue\n",
    "            else:\n",
    "                if i not in hmap:\n",
    "                    hmap[i] = 1\n",
    "                else:\n",
    "                    hmap[i] += 1\n",
    "        for j in hmap:\n",
    "            if hmap[j] == 1:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        if max(hmap) - min(hmap) < 5:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def checkDynasty(self, place: List[int]) -> bool:\n",
    "        place.sort()\n",
    "\n",
    "        gap_count = 0\n",
    "        zero_count = 0\n",
    "        pre = 0\n",
    "\n",
    "        for i in place:\n",
    "            if i == 0:\n",
    "                zero_count += 1\n",
    "            elif pre != 0:\n",
    "                if i > pre:\n",
    "                    gap_count += i - pre - 1\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            pre = i\n",
    "        \n",
    "        # print(place)\n",
    "        # print(f'{zero_count}, {gap_count}')\n",
    "            \n",
    "        return zero_count >= gap_count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
